Intro to Crypto 1 - localo

Category: Crypto
Difficulty: Hard
Author: black-simon

Description

What did you say?

nc hax1.allesctf.net 9400

Summery

The author provided a script server.py we send a private key to decrypt a fixed message: Quack! Quack! if this message decrypts to a sentence chosen by the author we get the flag.

Solution

My first approach was to come up with a general solution.
$m \equiv c^d\ (\textrm{mod}\ N)$ Since we control $d$ and $N$ a simple solution is:
$m \equiv c^k\ (\textrm{mod}\ c^k - m)$ And since for every divisor $t$ of $N$
$m \equiv c^d\ (\textrm{mod}\ t)$ is a solution, we "just" need to factor $c^k - m$ and if we find two prime-factors with their product is greater than $m$ we should get the flag. I factored it up to $k = 6$, but had no luck and the process was quite time consuming, therefore I knew it was not the ideal solution. I did some google searches and found this writeup from this years BSidesSF CTF it is basically the same problem, I tried to understand what is going on, and I guess I kind of got it, but to be honest I had already thought about discrete logarithms, but I thought, that it would be even harder to solve it that way, I still don't get why there are those special cases and how they work and I just copy-pasted the code and did some automation.

import numpy
from pyasn1.codec.der import encoder
from pyasn1.type.univ import SequenceOf
from pyasn1.type.univ import Integer as CompInt
import base64
import socket
def gen_cand(b,l):
    p = 2
    while log(p)/log(2) < b:
        np = next_prime(numpy.random.randint(2,l))
        p = p*np
    return p+1

def kk(b,l):
    while True:
       p = gen_cand(b,l)
       if is_prime(p):
           return p

M = 1067267517149537754067764973523953846272152062302519819783794287703407438588906504446261381994947724460868747474504670998110717117637385810239484973100105019299532993569
C = 6453808645099481754496697330465

Q = 2
bits = 559

E = 0
while E <3:
  P = kk(bits,10**6)
  N = P*Q
  gp("addprimes(%d)"%(P))
  sol = gp("znlog(%d, Mod(%d, %d))" % (M,C,N))
  if len(sol) == 0:
    continue
  D = Integer(sol)
  try:
    E = inverse_mod(D,(P-1) * (Q-1))
  except:
    continue

P = P.__int__()
Q = Q.__int__()
D = D.__int__()
N = N.__int__()
E = E.__int__()

print("P: %d"%P)
print("Q: %d"%Q)
print("E: %d"%E)
print("D: %d"%D)

seq = SequenceOf(componentType=CompInt())
enc = encoder.encode([0,N,E,D,P,Q,D % (P-1), D % (Q-1), inverse_mod(Q,P).__int__()],asn1Spec=SequenceOf(componentType=CompInt()))
pem = '-----BEGIN RSA PRIVATE KEY-----\n%s\n-----END RSA PRIVATE KEY-----\n' % base64.b64encode(enc)
s = socket.socket(
    socket.AF_INET, socket.SOCK_STREAM)
s.connect(("hax1.allesctf.net", 9400))
s.recv(1024)
s.send(pem+"\n")
s.recv(1024)
s.send("\n")
print(s.recv(1024))
print(s.recv(1024))

Mitigation

• upgrade your google skills 😉
• don't trust user input

Flag

CSCG{下一家烤鴨店在哪裡？}